package com.kuang.linkedlist;

/*  给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。    */

import java.util.HashMap;

/**
 * @author kjx
 */
public class GetIntersectionNode {

    //想不到好方法，就先用笨蛋方法
    //笨方法单单看时间复杂度其实也是O(n)，但是创建、存储、查找哈希表其实也是很耗时的，因此这个光荣地在leetcode上成功打败6%的用户
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //遍历A，存储到map中
        for (ListNode hailA = headA; hailA != null; hailA = hailA.next) {
            map.put(hailA.hashCode(), 1);
        }
        //遍历B，看看是否有相等
        for (ListNode hailB = headB; hailB != null; hailB = hailB.next) {
            if (map.get(hailB.hashCode()) != null) {
                return hailB;
            }
        }
        return null;
    }


    //下面用双指针
    //考虑到两个链表长度是不一样的，因此我们可以把两个链表拼接在一起遍历，相交的地方就是原先两个链表相交的地方
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pa = headA, pb = headB;
        while (pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }
}
